/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.linkedlist;

import org.junit.Test;

/**
 * <p>
 * 移除有序链表的重复元素,删除重复元素确保每个元素出现一次 
 * Given 1->1->2, return 1->2. 
 * Given 1->1->2->3->3, return 1->2->3.
 * </p>
 * 
 * @author towan
 * @email tongwenzide@163.com 2015年5月19日
 */
public class RemoveDuplicatesFromSortedList {

   public ListNode deleteDuplicates(ListNode head) {
       if(head==null ){
           return head;
       }
       //保存非重复元素的列表
       ListNode prev = head;
       ListNode curr = head.next;
       //开始扫描原有的链表
       while(curr!=null){
           //如果值不同，需要同时移动两个指针，相同值只需移动curr
           if(curr.val!=prev.val){
               prev = prev.next;
           }
           curr = curr.next;
           prev.next = curr;
       }
       return head;
    }
   
   @Test
   public void testCase1(){
       ListNode head = new ListNode(1);
       head.next = new ListNode(1);
       head.next.next = new ListNode(1);
       head.next.next.next = new ListNode(2);
       head.next.next.next.next = new ListNode(2);
       head.next.next.next.next.next = new ListNode(3);
       
       ListNode node = deleteDuplicates(head);
       while(node!=null){
           System.out.print(" "+node.val+"\t");
           node = node.next;
       }
   }
}


